Data in an associative memory or content addressable memory is not accessed by address as in conventional memories. Rather than being identified by location, the data is identified from properties inherent in its own value. To retrieve a word from associative store, a search key (or descriptor) is generated which represents particular values of all or some of the bits of the word to be retrieved. This word is presented to the associative memory and compared in parallel with the corresponding lock or tag bits of all stored words, and all words matching this key are signaled to be available. If the key lacks specificity or it is "loose", a large number of words will be accessed relating to this key. The memory might indicate the number of such words and the address thereof and would allow for examination of each of these words. The order in which they are examined is usually related to their order in the physical storage and, therefore, tells nothing of their value. Once a match is made with the key word, each of these words can be utilized or, if not wanted, flagged such that succeeding words can be retrieved.
An associative search can be fairly complex if the search key has only a few elements and the association is loose wherein there is a high probability of obtaining a large number of words that match the key. A more specific associative search would be that in which only one occurrence of a search key match exists. An example of this type of association is in the use of associative stores between levels in a memory hierarchy where the associative store is a scratch pad denoting the existance of a copy of a record in the next higher-level store. This is also the case with the use of associative storage in cache memory management.
In the logical structure of a fully associative memory, each bit therein is accessible for comparison with a desired bit of the key word. Therefore, the bits in the associative memory must be arranged in groups and each of the bits in each of these groups compared in parallel with the bits of the key word. The amount of circuitry required for very large associative memories can become quite unwieldily and expensive. Architectures of this type would not lend themselves to conventional processes such as those involved in fabrication of Dynamic Random Access Memories (D-RAM's). Therefore, there exists a need for a memory architecture that provides a certain degree of associative search without requiring the complicated circuitry of a fully associative memory.